import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-08
 * Time: 8:54
 */
public class RandomizedSet {
    private Map<Integer, Integer> map;
    private List<Integer> list;
    private Random random;
    /** Initialize your data structure here. */
    public RandomizedSet() {
//         hashMap 可以 O(1) 的插入和删除
//         但是不能等可能随机的返回一个数字, 要用到 数组
//         怎么将他们联系起来呢, map.put(val, index)
//         数组删除元素时, 将要删除的位置与最后一个位置元素进行替换, 删除最后一个元素, 就可以 O(1) 的删除一个元素
        this.map = new HashMap<>();
        this.list = new ArrayList<>();
        this.random = new Random();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (map.containsKey(val)){
            return false;
        }
        int index = list.size();
        // 注意 这里只能list.add, 新增加元素时, 不能 list.set(index, val)
        // 因为 list的size 只是 list 拥有的元素的个数
        // 并不是 list 所占空间的大小
        list.add(val);
        map.put(val, index);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val)){
            return false;
        }
        int index = map.get(val);
        int tail = list.size() - 1;
        list.set(index, list.get(tail));
        map.put(list.get(tail), index);
        // 注意这两个删除, 必须最后再删除
        // 因为可能原本集合里面就只剩一个元素了
        // 如果提前删除了, 那么后面可能会再加进来, 因为将最后一个元素替换了要删除的元素, 而正好这是同一个元素
        map.remove(val);
        list.remove(tail);
        return true;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        // 左开右闭
        int index = random.nextInt(list.size());
        return list.get(index);
    }
}